home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / X11 / xpaint-2.1.1 / hash.c < prev    next >
C/C++ Source or Header  |  1995-05-03  |  6KB  |  274 lines
  1. /* +-------------------------------------------------------------------+ */
  2. /* | Copyright 1992, David Koblas.                                     | */
  3. /* |   Permission to use, copy, modify, and distribute this software   | */
  4. /* |   and its documentation for any purpose and without fee is hereby | */
  5. /* |   granted, provided that the above copyright notice appear in all | */
  6. /* |   copies and that both that copyright notice and this permission  | */
  7. /* |   notice appear in supporting documentation.  This software is    | */
  8. /* |   provided "as is" without express or implied warranty.           | */
  9. /* +-------------------------------------------------------------------+ */
  10.  
  11. /*
  12. **  A Simple useful set of hash routines:
  13. **
  14. **      void    *HashCreate(int (*cmp)(void *, void*), void (*free)(void *), int nelem)
  15. **      -- Create a hash table with cmp() function, and optional free() function.
  16. **    void     HashDestroy(HashTable *tbl)
  17. **      -- Destroy the whole hash table
  18. **    void    *HashFind(HashTable *tbl, int value, void *val)
  19. **       -- Find an element in the hash table, returns NULL if not found
  20. **    int     HashAdd(HashTable *tbl, int value, void *val)
  21. **      -- Add an element to the table, returns non-zero on failure
  22. **    int     HashRemove(HashTable *tbl, int value, void *elem)
  23. **      -- Remove a particular hash entry from the table, pointer compairson
  24. **    int     HashAll(HashTable *tbl, int (*func)(void *))
  25. **      -- Apply function to all elements of the table, until func() returns non-zero
  26. */
  27.  
  28.  
  29. #include <stdio.h>
  30. #if 0
  31. #include <malloc.h>
  32. #else
  33. extern void free(void *);
  34. extern void *malloc(unsigned int);
  35. #endif
  36.  
  37. typedef struct hash_s {
  38.     int        *val;
  39.     struct hash_s    *left, *right, *same, **parentp;
  40. } HashElement;
  41.  
  42. typedef struct {
  43.     int        (*cmp)(void *, void *);
  44.     void        (*free)(void *);
  45.     HashElement    **table;
  46.     int        nelem;
  47. } HashTable;
  48.  
  49. /*
  50. **  Create a hashtable, with cmp() compare function, and free() free function
  51. **       with a hash table width of nelem, free can be null in which case the
  52. **       system free function will be used.
  53. */
  54. void    *HashCreate(int (*cmp)(void *, void *), void (*free)(void *), int nelem)
  55. {
  56.     HashTable    *new;
  57.     int        i;
  58.  
  59.     new = (HashTable*)malloc(sizeof(HashTable));
  60.     new->nelem = nelem;
  61.     new->cmp   = cmp;
  62.     new->free  = free;
  63.     new->table = (HashElement **)malloc(nelem * sizeof(HashElement*));
  64.  
  65.     for (i = 0; i < nelem; i++)
  66.         new->table[i] = NULL;
  67.  
  68.     return (void*)new;
  69. }
  70.  
  71. static void hashDestory(void (*func)(void *), HashElement *entry)
  72. {
  73.     if (entry->left != NULL) {
  74.         hashDestory(func, entry->left);
  75.         free(entry->left);
  76.     }
  77.     if (entry->right != NULL) {
  78.         hashDestory(func, entry->right);
  79.         free(entry->right);
  80.     }
  81.     if (entry->same != NULL) {
  82.         hashDestory(func, entry->same);
  83.         free(entry->same);
  84.     }
  85.  
  86.     if (entry->val)
  87.         func(entry->val);
  88. }
  89.  
  90. /*
  91. **  Free the entire hash table, and all elements
  92. */
  93. void    HashDestroy(HashTable *tbl)
  94. {
  95.     int        i;
  96.  
  97.     if (tbl == NULL)
  98.         return;
  99.  
  100.     for (i = 0; i < tbl->nelem; i++) {
  101.         if (tbl->table[i] != NULL) {
  102.             hashDestory(tbl->free ? tbl->free : free, tbl->table[i]);
  103.             free(tbl->table[i]);
  104.         }
  105.     }
  106.     free(tbl->table);
  107.     free(tbl);
  108. }
  109.  
  110. /*
  111. **  Find a particular element in the hash table, returns NULL if it isn't found
  112. */
  113. void    *HashFind(HashTable *tbl, int value, void *val)
  114. {
  115.     HashElement    *cur;
  116.     int        v;
  117.  
  118.     if (tbl == NULL)
  119.         return NULL;
  120.  
  121.     cur = tbl->table[value];
  122.  
  123.     while (cur != NULL) {
  124.         if ((v = tbl->cmp(cur->val, val)) == 0)
  125.             return cur->val;
  126.  
  127.         if (v < 0)
  128.             cur = cur->left;
  129.         else
  130.             cur = cur->right;
  131.     }
  132.  
  133.     return NULL;
  134. }
  135.  
  136. /*
  137. **  And a new element to the has table, returns non-zero on failure
  138. */
  139. int    HashAdd(HashTable *tbl, int value, void *val)
  140. {
  141.     HashElement    *new = (HashElement*)malloc(sizeof(HashElement));
  142.     HashElement    *cur = tbl->table[value];
  143.     HashElement    **prev;
  144.     int        v;
  145.  
  146.     if (new == NULL || tbl == NULL)
  147.         return 1;
  148.  
  149.     new->left    = NULL; 
  150.     new->right   = NULL; 
  151.     new->same    = NULL;
  152.     new->val     = val;
  153.     new->parentp = NULL;
  154.  
  155.     prev = &tbl->table[value];
  156.     while (cur != NULL) {
  157.         if ((v = tbl->cmp(cur->val, val)) < 0) {
  158.             prev = &cur->left;
  159.             cur  = cur->left;
  160.         } else if (v > 0) {
  161.             prev = &cur->right;
  162.             cur  = cur->right;
  163.         } else {
  164.             prev = &cur->same;
  165.             new->same = cur->same;
  166.             if (cur->same != NULL)
  167.                 cur->same->parentp = &new->same;
  168.             break;
  169.         }
  170.     }
  171.     *prev = new;
  172.     new->parentp = prev;
  173.  
  174.     return 0;
  175. }
  176.  
  177. static HashElement     *find(HashElement *pos, void *elem)
  178. {
  179.     HashElement    *v;
  180.  
  181.     if (pos == NULL)
  182.         return NULL;
  183.  
  184.     if (pos->val == elem)
  185.         return pos;
  186.     if (pos->left != NULL && (v = find(pos->left, elem)) != NULL)
  187.         return v;
  188.     if (pos->right != NULL && (v = find(pos->right, elem)) != NULL)
  189.         return v;
  190.     if (pos->same != NULL && (v = find(pos->same, elem)) != NULL)
  191.         return v;
  192.     return NULL;
  193. }
  194.  
  195. /*
  196. **  Remove a particular element from the hash table, done using pointer compares
  197. */
  198. int    HashRemove(HashTable *tbl, int value, void *elem)
  199. {
  200.     HashElement    *v;
  201.  
  202.     if (elem == NULL || tbl == NULL)
  203.         return 1;
  204.  
  205.     if ((v = find(tbl->table[value], elem)) == NULL) 
  206.         return 0;
  207.  
  208.     if (v->same != NULL) {
  209.         /*
  210.         **  Same links are not allowed to have left & right children
  211.         **   so just inherit the parent's children.
  212.         */
  213.         if (v->left != NULL)
  214.             v->left->parentp = &v->same->left;
  215.         if (v->right != NULL)
  216.             v->right->parentp = &v->same->right;
  217.         v->same->left = v->left;
  218.         v->same->right = v->right;
  219.  
  220.         *v->parentp = v->same;
  221.         v->same->parentp = v->parentp;
  222.     } else if (v->left != NULL) {
  223.         *v->parentp = v->left;
  224.         v->left->parentp = v->parentp;
  225.         if (v->right != NULL) {
  226.             HashElement    *cur = v->left, **prev = &v->left;
  227.             while (cur != NULL) {
  228.                 if (tbl->cmp(cur->val, v->right->val) < 0) {
  229.                     prev = &cur->left;
  230.                     cur  =  cur->left;
  231.                 } else {
  232.                     prev = &cur->right;
  233.                     cur  =  cur->right;
  234.                 }
  235.             }
  236.             *prev = v->right;
  237.             v->right->parentp = prev;
  238.         }
  239.     } else {
  240.         /* no left side, just attach the right */
  241.         *v->parentp = v->right;
  242.         if (v->right != NULL)
  243.             v->right->parentp = v->parentp;
  244.     }
  245.     free(v);
  246.  
  247.     return 1;
  248. }
  249.  
  250. static int overAll(HashElement *elem, int (*func)(void *)) 
  251. {
  252.     if (elem == NULL)
  253.         return 0;
  254.     if (elem->val != NULL)
  255.         func(elem->val);
  256.  
  257.     return overAll(elem->left, func)  || 
  258.            overAll(elem->right, func) ||
  259.            overAll(elem->same, func);
  260. }
  261.  
  262. int    HashAll(HashTable *tbl, int (*func)(void *))
  263. {
  264.     int    i;
  265.  
  266.     if (tbl == NULL)
  267.         return 0;
  268.  
  269.     for (i = 0; i < tbl->nelem; i++)
  270.         if (overAll(tbl->table[i], func))
  271.             return 1;
  272.     return 0;
  273. }
  274.